package com.arrays.a2;

/*
300. 最长递增子序列

 */
public class LengthOfLIS {

    /*
    1. 动态规划
     */
    public static int method01(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        //记录升序的个数
        int[] tmp = new int[len];
        int res = 0;
        /*
        1 5 2 4 3

         */

        for (int i = 0; i < len; i++) {
            //内层循环，确保升序 满足nums[j] < nums[i] 的向tmp中记录
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    tmp[i] = Math.max(tmp[i], tmp[j] + 1);
                }
            }
            res = Math.max(res, tmp[i]);
        }
        return res + 1;//初始是从0开始记录的，所以结果+1

    }

    public static void main(String[] args) {
        int[] a = {10, 9, 2, 5, 3, 7, 101, 18};//4
        int[] b = {0, 3, 1, 6, 2, 2, 7};       //4
        int[] c = {0, 1, 0, 3, 2, 3};           //4
        int[] d = {1, 3, 6, 7, 9, 4, 10, 5, 6}; //6
        int[] e = {1, 5, 2, 4, 3};

        int res = method01(e);
        System.out.println(res);
    }
}
